1. Field of Invention
The invention relates to a method of analyzing and quantifying intrinsic parallelism of an algorithm.
2. Related Art
Amdahl's law (G. M. Amdahl, “Validity of single-processor approach to achieving large-scale computing capability,” Proc. of AFIPS Conference, pp. 483-485, 1967) introduced a theoretical maximum speedup of parallelization of a software program. The theoretical maximum speedup is determined by the ratio of sequential part within the program, since the sequential part cannot be paralleled due to the high data dependencies. Amdahl's law provided a brief and initial high level idea for characterizing parallelisms. However, the parallelism measured by this technique depends rather on the target platforms but not on the algorithms themselves. Therefore, such a parallelism measurement is extrinsic to the algorithms and is biased by the target platforms.
In a similar manner, the graph-based technique (V. Escuder, R. Duran, R. Rico, “Quantifying ILP by means of graph theory,” Proceedings of the 2nd international conference on performance evaluation methodologies and tools, 2007) quantifies the instruction level parallelism (ILP) of programs based on the graph theory. This technique initially represents a sequence of instructions by data dependence matrix, D. Subsequently, the critical path length of the program is determined by the matrix multiplication of D. This technique is more specific for processor-oriented platforms. Hence, the quantifications of ILP are not intrinsic to algorithms but depend on the targeted platforms and compiler used.
Prihozhy et al defined the parallelization potential based on the ratio between the computational complexity and the critical path length of algorithms also capable of estimating the degree of parallelism (A. Prihozhy, M. Mattavelli and D. Mlynek, “Evaluation of the parallelization potential for efficient multimedia implementations: dynamic evaluation of algorithm critical path,” IEEE Trans. on Circuits and Systems for Video Technology, pp. 593-608, Vol. 15, No. 5, May 2005). They measured the complexity by means of the total number of operations. The critical path length is then defined as the largest number of operations that have to be sequentially performed. As compared to Amdahl's law and the ILP method, the parallelization potential based on the number of operations reveals more intrinsic parallelism measurements but of course at a lower data granularity. However, this method can not reveal the most intrinsic parallelism of algorithms, since the number of operations and critical path length are calculated based on data flow execution graphs (DFEG) generated by C/C++ programs, which could be biased by programming styles and data structures.
On the other hand, the causation trace graphs generated by dataflow models of algorithms can reveal more intrinsic dependency of algorithms and hence algorithmic parallelism. In general, the relatively thin and linear part of a causation trace graph is composed of more sequential operations and the wider part contains higher degree of parallelism. In the paper (J. W. Janneck, D. Miller and D. B. Parlour, “Profiling dataflow programs,” Proceeding of IEEE ICME 2008, pp. 1065-1068, June 2008), the parallelizability of the computation can then be measured to reveal the work done on average at the same time. However, this method is incapable of quantifying the exact degree of parallelism.